package com.mango.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序
 * 空间复杂度：O(1)
 * 时间复杂度：O(n2)
 * 思路：(把数组分为左和右，左边的默认有顺序，右边的数插入到左边合适的位置）
 * 例子：13,7,4,6,9,24,12
 *
 * [7, 13, 4, 6, 9, 24, 12]
 * [7, 4, 13, 6, 9, 24, 12]
 * [4, 7, 13, 6, 9, 24, 12]
 * [4, 7, 6, 13, 9, 24, 12]
 * [4, 6, 7, 13, 9, 24, 12]
 * [4, 6, 7, 9, 13, 24, 12]
 * [4, 6, 7, 9, 13, 12, 24]
 * [4, 6, 7, 9, 12, 13, 24]
 * [4, 6, 7, 9, 12, 13, 24]
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] nums = {13,7,4,6,9,24,12};
        System.out.println("old:"+Arrays.toString(nums));
        System.out.println("result:"+Arrays.toString(sort(nums)));
    }
    // 插入排序
    public static int[] sort(int[] nums){
        for(int i=0;i<nums.length;i++){
            for(int j=i;j>0;j--){
                if(nums[j] < nums[j-1]){
                    swap(nums,j,j-1);
                    System.out.println(i+")"+Arrays.toString(nums));
                }else{
                    break;
                }
            }
        }
        return nums;
    }
    // 交换数组下标
    public static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
